#pragma once

///单链表类型定义
template <typename E>
struct LNode
{
    E data;
    LNode *next;
};

// typedef LNode *LinkList;//c
template <typename E>
using LinkList = LNode<E> *;

///单链表基本操作

///初始化空表 Initlist（&L）
template <typename E>
void InitList(LinkList<E> &L)
{
    L = new LNode<E>;
    L->next = nullptr;
}

///链表插入 LinkInsert（&L,i,e）
template <typename E>
void ListInsert(LinkList<E> &L, int i, E e)
{
    //查找第i-1个结点p
    //LinkList<E> p=L;
    auto p = L;
    int j = 0;
    while (p && j < i - 1)
    {
        p = p->next;
        ++j;
    }

    //若找到，则在p之后插入e，否则抛出异常
    if (p && j == i - 1)
    {
        //新建结点 s
        auto s = new LNode<E>;
        s->data = e;
        //在p之后插入s
        s->next = p->next;
        p->next = s;
    }
    else
    {
        throw "Invalid i";
    }
}
///链表删除 ListDelete(&L,i,&e)
template <typename E>
void ListDelete(LinkList<E> &L, int i, E &e)
{
    //查找第i-1个结点 p
    auto p = L;
    int j = 0;
    while (p && j < i - 1)
    {
        p = p->next;
        ++j;
    }
    //若找到且存在第i-1个结点，则删除，否则抛出异常
    if (p && j == i - 1 && p->next)
    {
        auto q = p->next;
        p->next = q->next;
        e = q->data;
        delete q;
    }
    else
    {
        throw "Invalid i";
    }
}
